/*
 * bst/parent_node.hh - Node with parent implementation.
 * Copyright (C) 2008  Mikhail Vorozhtsov
 * See the LICENSE section of the README file for details.
 */

/* $Id$ */

#ifndef HEADER_LIBBST_MJ_PARENT_NODE_HH
#define HEADER_LIBBST_MJ_PARENT_NODE_HH

#include HEADER (LIBBST_PREFIX,base.hh)

START_NAMESPACE (LIBBST_NS)

struct basic_parent_node_t : public basic_node_t
{
private:
  typedef basic_parent_node_t node_t;

protected:
  ptr_t parent;

public:
  INLINE
  node_t *
  get_parent () const
  {
    return (node_t *) parent.raw;
  }

  INLINE
  void
  set_parent (node_t *x)
  {
    parent.raw = (u64_t) x;
  }
};

template <typename T, class P, u64_t OFFSET, typename CMP>
class base_parent_node_t : public base_node_t<T, P, OFFSET, CMP>
{
public:
  template <typename TREE, typename NODE>
  INLINE
  NODE *
  get_parent (TREE *tree UNUSED, NODE *top UNUSED)
  {
    return (NODE *) P::get_parent ();
  }

  template <typename TREE, typename NODE>
  NODE *
  rotate_left (TREE *tree, NODE *parent)
  {
    NODE *pivot = ((NODE *) this)->get_right ();
    NODE *pivot_left = pivot->get_left ();

    pivot->set_parent (parent);
    pivot->set_left (this);
    this->set_parent (pivot);
    this->set_right (pivot_left);

    if (pivot_left)
      pivot_left->set_parent (this);

    if (parent)
      {
        if (this == parent->get_left ())
          parent->set_left (pivot);
        else
          parent->set_right (pivot);
      }
    else
      tree->set_root (pivot);

    return pivot;
  }

  template <typename TREE, typename NODE>
  NODE *
  rotate_right (TREE *tree, NODE *parent)
  {
    NODE *pivot = ((NODE *) this)->get_left ();
    NODE *pivot_right = pivot->get_right ();

    pivot->set_parent (parent);
    pivot->set_right (this);
    this->set_parent (pivot);
    this->set_left (pivot_right);

    if (pivot_right)
      pivot_right->set_parent (this);

    if (parent)
      {
        if (this == parent->get_left ())
          parent->set_left (pivot);
        else
          parent->set_right (pivot);
      }
    else
      tree->set_root (pivot);

    return pivot;
  }
};

template <typename T, class P = T, u64_t OFFSET = 0,
          typename CMP = compare<T, T> >
struct parent_node_t : public base_parent_node_t<T, P, OFFSET, CMP>
{
private:
  typedef parent_node_t node_t;
  typedef base_node_t<T, P, OFFSET, CMP> parent_t;

public:
  __LIBBST_MJ_NODE_WRAPPERS
  __LIBBST_MJ_NODE_ORD_PREV
  __LIBBST_MJ_NODE_ORD_NEXT

public:
  template <typename TREE>
  void
  insert (TREE *tree, node_t *parent, bool left_p, node_t *prev_or_next UNUSED)
  {
    if (parent)
      {
        if (left_p)
          parent->set_left (this);
        else
          parent->set_right (this);
      }
    else
      tree->set_root (this);

    this->set_parent (parent);
    this->set_left (NULL);
    this->set_right (NULL);
  }

  template <typename TREE>
  void
  remove (TREE *tree, node_t *parent, bool left_p, node_t *prev_or_next UNUSED)
  {
    if (parent)
      {
        if (left_p)
          parent->set_left (NULL);
        else
          parent->set_right (NULL);
      }
    else
      tree->set_root (NULL);
  }

  template <typename TREE>
  node_t *
  replace_with_pred (TREE *tree, node_t *parent, bool left_p, node_t *pred,
                     node_t *pred_parent, node_t *&succ UNUSED)
  {
    node_t *left = this->get_left ();
    node_t *right = this->get_right ();
    node_t *pred_left = pred->get_left ();

    pred->set_parent (parent);
    pred->set_right (right);

    if (right)
      right->set_parent (pred);

    if (pred_parent != this)
      {
        pred->set_left (left);
        left->set_parent (pred);
        pred_parent->set_right (pred_left);

        if (pred_left)
          pred_left->set_parent (pred_parent);
      }

    if (parent)
      {
        if (left_p)
          parent->set_left (pred);
        else
          parent->set_right (pred);
      }
    else
      tree->set_root (pred);

    return pred_left;
  }

  template <typename TREE>
  node_t *
  replace_with_succ (TREE *tree, node_t *parent, bool left_p, node_t *succ,
                     node_t *succ_parent, node_t *prev_or_next UNUSED)
  {
    node_t *right = this->get_right ();
    node_t *succ_right = succ->get_right ();

    succ->set_parent (parent);
    succ->set_left (NULL);

    if (succ_parent != this)
      {
        succ->set_right (right);
        right->set_parent (succ);
        succ_parent->set_left (succ_right);

        if (succ_right)
          succ_right->set_parent (succ_parent);
      }

    if (parent)
      {
        if (left_p)
          parent->set_left (succ);
        else
          parent->set_right (succ);
      }
    else
      tree->set_root (succ);

    return succ_right;
  }

  template <typename TREE>
  void
  replace (TREE *tree, node_t *with)
  {
    node_t *parent = (node_t *) P::get_parent ();
    node_t *left = this->get_left ();
    node_t *right = this->get_right ();

    if (parent)
      {
        if (parent->get_left () == this)
          parent->set_left (with);
        else
          parent->set_right (with);
      }
    else
      tree->set_root (with);

    with->set_parent (parent);
    with->set_left (left);
    with->set_right (right);

    if (left)
      left->set_parent (with);
    if (right)
      right->set_parent (with);
  }
};

struct basic_parent_next_node_t : public basic_parent_node_t
{
private:
  typedef basic_parent_next_node_t node_t;

protected:
  ptr_t next;

public:
  INLINE
  node_t *
  get_next () const
  {
    return (node_t *) next.raw;
  }

  INLINE
  void
  set_next (node_t *x)
  {
    next.raw = (u64_t) x;
  }
};

template <typename T, class P = T, u64_t OFFSET = 0,
          typename CMP = compare<T, T> >
struct parent_next_node_t : public base_parent_node_t<T, P, OFFSET, CMP>
{
private:
  typedef parent_next_node_t node_t;
  typedef base_node_t<T, P, OFFSET, CMP> parent_t;

public:
  __LIBBST_MJ_NODE_WRAPPERS
  __LIBBST_MJ_NODE_ORD_PREV

  template <typename TREE>
  node_t *
  get_next (TREE *tree UNUSED) const
  {
    return (node_t *) P::get_next ();
  }

public:
  template <typename TREE>
  void
  insert (TREE *tree, node_t *parent, bool left_p, node_t *prev_or_next)
  {
    if (parent)
      {
        if (left_p)
          {
            parent->set_left (this);
            this->set_next (parent);
            if (prev_or_next)
              prev_or_next->set_next (this);
          }
        else
          {
            parent->set_right (this);
            parent->set_next (this);
            this->set_next (prev_or_next);
          }
      }
    else
      {
        this->set_next (NULL);
        tree->set_root (this);
      }

    this->set_parent (parent);
    this->set_left (NULL);
    this->set_right (NULL);
  }

  template <typename TREE>
  void
  remove (TREE *tree, node_t *parent, bool left_p, node_t *prev_or_next)
  {
    if (parent)
      {
        if (left_p)
          {
            parent->set_left (NULL);
            if (prev_or_next)
              prev_or_next->set_next (parent);
          }
        else
          {
            parent->set_right (NULL);
            parent->set_next (P::get_next ());
          }
      }
    else
      tree->set_root (NULL);
  }

  template <typename TREE>
  node_t *
  replace_with_pred (TREE *tree, node_t *parent, bool left_p, node_t *pred,
                     node_t *pred_parent, node_t *&succ UNUSED)
  {
    node_t *left = this->get_left ();
    node_t *right = this->get_right ();
    node_t *pred_left = pred->get_left ();

    pred->set_next (P::get_next ());
    pred->set_parent (parent);
    pred->set_right (right);

    if (right)
      right->set_parent (pred);

    if (pred_parent != this)
      {
        pred->set_left (left);
        left->set_parent (pred);
        pred_parent->set_right (pred_left);

        if (pred_left)
          pred_left->set_parent (pred_parent);
      }

    if (parent)
      {
        if (left_p)
          parent->set_left (pred);
        else
          parent->set_right (pred);
      }
    else
      tree->set_root (pred);

    return pred_left;
  }

  template <typename TREE>
  node_t *
  replace_with_succ (TREE *tree, node_t *parent, bool left_p, node_t *succ,
                     node_t *succ_parent, node_t *prev_or_next)
  {
    node_t *right = this->get_right ();
    node_t *succ_right = succ->get_right ();

    succ->set_parent (parent);
    succ->set_left (NULL);

    if (succ_parent != this)
      {
        succ->set_right (right);
        right->set_parent (succ);
        succ_parent->set_left (succ_right);

        if (succ_right)
          succ_right->set_parent (succ_parent);
      }

    if (parent)
      {
        if (left_p)
          {
            parent->set_left (succ);
            if (prev_or_next)
              prev_or_next->set_next (succ);
          }
        else
          {
            parent->set_right (succ);
            parent->set_next (succ);
          }
      }
    else
      tree->set_root (succ);

    return succ_right;
  }

  template <typename TREE>
  void
  replace (TREE *tree, node_t *with)
  {
    node_t *parent = (node_t *) P::get_parent ();
    node_t *left = this->get_left ();
    node_t *right = this->get_right ();
    node_t *prev = this->get_prev (tree);

    if (parent)
      {
        if (parent->get_left () == this)
          parent->set_left (with);
        else
          parent->set_right (with);
      }
    else
      tree->set_root (with);

    with->set_parent (parent);
    with->set_left (left);
    with->set_right (right);
    with->set_next ((node_t *) P::get_next ());

    if (left)
      left->set_parent (with);
    if (right)
      right->set_parent (with);
    if (prev)
      prev->set_next (with);
  }
};

struct basic_parent_pn_node_t : public basic_parent_next_node_t
{
private:
  typedef basic_parent_pn_node_t node_t;

protected:
  ptr_t prev;

public:
  INLINE
  node_t *
  get_prev () const
  {
    return (node_t *) prev.raw;
  }

  INLINE
  void
  set_prev (node_t *x)
  {
    prev.raw = (u64_t) x;
  }
};

template <typename T, class P = T, u64_t OFFSET = 0,
          typename CMP = compare<T, T> >
struct parent_pn_node_t : public base_parent_node_t<T, P, OFFSET, CMP>
{
private:
  typedef parent_pn_node_t node_t;
  typedef base_node_t<T, P, OFFSET, CMP> parent_t;

public:
  __LIBBST_MJ_NODE_WRAPPERS

  template <typename TREE>
  node_t *
  get_prev (TREE *tree UNUSED) const
  {
    return (node_t *) P::get_prev ();
  }

  template <typename TREE>
  node_t *
  get_next (TREE *tree UNUSED) const
  {
    return (node_t *) P::get_next ();
  }

protected:
  void
  remove ()
  {
    node_t *prev = (node_t *) P::get_prev ();
    node_t *next = (node_t *) P::get_next ();

    if (prev)
      prev->set_next (next);
    if (next)
      next->set_prev (prev);
  }

public:
  template <typename TREE>
  void
  insert (TREE *tree, node_t *parent, bool left_p, node_t *prev_or_next)
  {
    if (parent)
      {
        if (left_p)
          {
            parent->set_left (this);
            parent->set_prev (this);
            this->set_prev (prev_or_next);
            this->set_next (parent);
            if (prev_or_next)
              prev_or_next->set_next (this);
          }
        else
          {
            parent->set_right (this);
            parent->set_next (this);
            this->set_prev (parent);
            this->set_next (prev_or_next);
            if (prev_or_next)
              prev_or_next->set_prev (this);
          }
      }
    else
      {
        this->set_prev (NULL);
        this->set_next (NULL);
        tree->set_root (this);
      }

    this->set_parent (parent);
    this->set_left (NULL);
    this->set_right (NULL);
  }

  template <typename TREE>
  void
  remove (TREE *tree, node_t *parent, bool left_p, node_t *prev_or_next UNUSED)
  {
    this->remove ();

    if (parent)
      {
        if (left_p)
            parent->set_left (NULL);
        else
          parent->set_right (NULL);
      }
    else
      tree->set_root (NULL);
  }

  template <typename TREE>
  node_t *
  replace_with_pred (TREE *tree, node_t *parent, bool left_p, node_t *pred,
                     node_t *pred_parent, node_t *&succ UNUSED)
  {
    node_t *left = this->get_left ();
    node_t *right = this->get_right ();
    node_t *pred_left = pred->get_left ();

    this->remove ();
    pred->set_parent (parent);
    pred->set_right (right);

    if (right)
      right->set_parent (pred);

    if (pred_parent != this)
      {
        pred->set_left (left);
        left->set_parent (pred);
        pred_parent->set_right (pred_left);

        if (pred_left)
          pred_left->set_parent (pred_parent);
      }

    if (parent)
      {
        if (left_p)
          parent->set_left (pred);
        else
          parent->set_right (pred);
      }
    else
      tree->set_root (pred);

    return pred_left;
  }

  template <typename TREE>
  node_t *
  replace_with_succ (TREE *tree, node_t *parent, bool left_p, node_t *succ,
                     node_t *succ_parent, node_t *prev_or_next UNUSED)
  {
    node_t *right = this->get_right ();
    node_t *succ_right = succ->get_right ();

    this->remove ();
    succ->set_parent (parent);
    succ->set_left (NULL);

    if (succ_parent != this)
      {
        succ->set_right (right);
        right->set_parent (succ);
        succ_parent->set_left (succ_right);

        if (succ_right)
          succ_right->set_parent (succ_parent);
      }

    if (parent)
      {
        if (left_p)
          parent->set_left (succ);
        else
          parent->set_right (succ);
      }
    else
      tree->set_root (succ);

    return succ_right;
  }

  template <typename TREE>
  void
  replace (TREE *tree UNUSED, node_t *with)
  {
    node_t *parent = (node_t *) P::get_parent ();
    node_t *left = this->get_left ();
    node_t *right = this->get_right ();
    node_t *prev = (node_t *) P::get_prev ();
    node_t *next = (node_t *) P::get_next ();

    if (parent)
      {
        if (parent->get_left () == this)
          parent->set_left (with);
        else
          parent->set_right (with);
      }
    else
      tree->set_root (with);

    with->set_parent (parent);
    with->set_left (left);
    with->set_right (right);

    if (left)
      left->set_parent (with);
    if (right)
      right->set_parent (with);

    with->set_prev (prev);
    with->set_next (next);
    
    if (prev)
      prev->set_next (with);
    if (next)
      next->set_prev (with);
  }
};

END_NAMESPACE

#endif /* HEADER_LIBBST_MJ_PARENT_NODE_HH */

